package com.darrenchan.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-20 11:06
 */
public class QLint197 {
    public long permutationIndex(int[] A) {
        int[] results = new int[2];

        List<Integer> AA = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            AA.add(A[i]);
        }
        Arrays.sort(A);
        dfs(A, AA, new boolean[A.length], new ArrayList<>(), results);

        return results[1];
    }

    private void dfs(int[] A, List<Integer> AA, boolean[] visited, List<Integer> subsets, int[] results) {
        if(subsets.size() == A.length) {
            results[0]++;
            if(subsets.equals(AA)) {
                results[1] = results[0];
            }
        }

        for (int i = 0; i < A.length; i++) {
            if(visited[i]) {
                continue;
            }

            subsets.add(A[i]);
            visited[i] = true;
            dfs(A, AA, visited, subsets, results);
            visited[i] = false;
            subsets.remove(subsets.size() - 1);
        }
    }

}
